package com.xiaoyg.algorithm;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public static void main(String[] args) {
        int [] preorder = new int []{3,9,20,15,7};
        int [] inorder = new int[]{9,3,15,20,7};

        TreeNode treeNode = buildTree(preorder, inorder);
        System.out.println(treeNode);
    }

    public  static Map<Integer,Integer> valToIndexMap = new HashMap<>();

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i< inorder.length;i++){
            valToIndexMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }

    public static TreeNode build(int [] preorder, int preStart,int preEnd, int []inorder, int inStart,int inEnd){
        if (preStart > preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        int index = valToIndexMap.get(rootVal);
        TreeNode root = new TreeNode(rootVal);

        int leftSize = index - inStart;

        root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart,index - 1);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
        return root;
    }

}


/*
*
 * Definition for a binary tree node.
  public class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
*/
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}